<HTML>
<!--
     Copyright (c) Jeremy Siek 2000

     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>EdgeListGraph</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
        ALINK="#ff0000">
<IMG SRC="../../../boost.png"
     ALT="C++ Boost" width="277" height="86">

<BR Clear>


<H2><A NAME="concept:EdgeListGraph"></A>
EdgeListGraph
</H2>

The EdgeListGraph concept refines the <a href="./Graph.html">Graph</a>
concept, and adds the requirement for efficient access to all the
edges in the graph.


<H3>Refinement of</H3>

<a href="./Graph.html">Graph</a>


<h3>Notation</h3>

<Table>
<TR>
<TD><tt>G</tt></TD>
<TD>A type that is a model of EdgeListGraph.</TD>
</TR>

<TR>
<TD><tt>g</tt></TD>
<TD>An object of type <tt>G</tt>.</TD>
</TR>

<TR>
<TD><tt>e</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
</TR>

</table>

<H3>Associated Types</H3>

<table border>

<tr>
<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
 This tag type must be convertible to <tt>edge_list_graph_tag</tt>.
</td>
</tr>

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::edge_iterator</pre>
An edge iterator (obtained via <TT>edges(g)</TT>) provides access to
all of the edges in a graph. An edge iterator type must meet the
requirements of <a
href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.  The
value type of the edge iterator must be the same as the edge
descriptor of the graph.

<tr>
<td><pre>boost::graph_traits&lt;G&gt;::edges_size_type</pre>
The unsigned integer type used to represent the number of edges in the
graph.
</td>
</tr>

</table>

<h3>Valid Expressions</h3>

<table border>

<tr>
<TD><a name="sec:edges"><TT>edges(g)</TT></a></TD>
<TD>Returns an iterator-range providing access to all
     the edges in the graph <TT>g</TT>.<br>
Return type: <TT>std::pair&lt;edge_iterator, edge_iterator&gt;</TT>
</td>
</TR>

<tr>
<TD><TT>num_edges(g)</TT></TD>
<TD>Returns the number of edges in the graph <TT>g</TT>.<br>
Return type: <TT>edges_size_type</TT>
</td>
</TR>

<tr>
<TD><TT>source(e, g)</TT></TD>
<TD>
Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i>
represented by <TT>e</TT>.<br>
Return type: <TT>vertex_descriptor</TT>
</td>
</tr>

<tr>
<TD><TT>target(e, g)</TT></TD>
<TD>
Returns the vertex descriptor for
<i>v</i> of the edge <i>(u,v)</i> represented by  <TT>e</TT>.<br>
Return type: <TT>vertex_descriptor</TT>
</TD>
</TR>

</TABLE>


<H3>Models</H3>

<UL>
<LI><a href="./adjacency_list.html"><TT>adjacency_list</TT></a></LI>
<LI><a href="./edge_list.html"><TT>edge_list</TT></a></LI>
</UL>


<H3>Complexity guarantees</H3>

The <TT>edges()</TT>, <TT>source()</TT>, and <TT>target()</TT> functions
must all return in constant time.


<H3>See Also</H3>

<a href="./graph_concepts.html">Graph concepts</a>

<H3>Concept Checking Class</H3>

<P>
<PRE>
  template &lt;class G&gt;
  struct EdgeListGraphConcept
  {
    typedef typename boost::graph_traits&lt;G&gt;::edge_iterator
      edge_iterator;
    void constraints() {
      BOOST_CONCEPT_ASSERT(( GraphConcept&lt;G&gt; ));
      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;edge_iterator&gt; ));

      p = edges(g);
      E = num_edges(g);
      e = *p.first;
      u = source(e, g);
      v = target(e, g);
      const_constraints(g);
    }
    void const_constraints(const G&amp; g) {
      p = edges(g);
      E = num_edges(g);
      e = *p.first;
      u = source(e, g);
      v = target(e, g);
    }
    std::pair&lt;edge_iterator,edge_iterator&gt; p;
    typename boost::graph_traits&lt;G&gt;::vertex_descriptor u, v;
    typename boost::graph_traits&lt;G&gt;::edge_descriptor e;
    typename boost::graph_traits&lt;G&gt;::edges_size_type E;
    G g;
  };
</PRE>


<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2000-2001</TD><TD>
<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
